package medium.slidewindow;

/**
 * <a href="https://leetcode-cn.com/problems/max-consecutive-ones-iii">1004. 最大连续1的个数 III</a>
 * 给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
 * 返回仅包含 1 的最长（连续）子数组的长度。
 * 示例 1：
 *   输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
 *   输出：6
 *   解释：[1,1,1,0,0,1,1,1,1,1,1] 数字从 0 翻转到 1，最长的子数组长度为 6。
 * 示例 2：
 *   输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
 *   输出：10
 *   解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 数字从 0 翻转到 1，最长的子数组长度为 10。
 * 提示：
 *   1 <= A.length <= 20000
 *   0 <= K <= A.length
 *   A[i] 为 0 或 1
 * 解题思路：
 *   1. 当数组大小等于k时，直接返回k即可；
 *   2. 右指针每次右移一位，统计当前窗口中0的个数（+(a[right]^1)，表示：遇0则加1,遇1则加0）
 *   3. 当0的个数大于k时，左指针需要左移，移除的元素若等于0，则0的个数减1
 *   4. 当右指针移到数组最后一个元素后，结束循环，返回右指针-左指针，即为最大连续1的个数。
 * @author 刘学松
 * @date 2021/2/19 18:42
 */
public class 最大连续1的个数III {
    public static void main(String[] args) {
        int[] a = {0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1};
        int k = 3;
        System.out.println(longestOnes(a, k));
    }

    public static int longestOnes(int[] a, int k) {
        int length = a.length;
        if (k == length) {
            return k;
        }

        int left = 0;
        int right = 0;
        int zeros = 0;
        while (right < length) {
            zeros += a[right] ^ 1;
            if (zeros > k && a[left++] == 0) {
                --zeros;
            }
            ++right;
        }

        return right - left;
    }
}
